package com.leetcode.根据数据结构分类.并查集;

import java.util.HashSet;
import java.util.Set;

/**
 * @author: xiaomi
 * @date: 2021/1/15
 * @description: 947. 移除最多的同行或同列石头
 * https://leetcode-cn.com/problems/most-stones-removed-with-same-row-or-column/
 */
public class B_947_移除最多的同行或同列石头 {

	public static void main(String[] args) {
//		int[][] stones = {{0, 0}, {0, 1}, {1, 0}, {1, 2}, {2, 1}, {2, 2}};
//		int[][] stones = {{0, 1}, {1, 0}, {1, 1}};
		int[][] stones = {{6, 4}, {0, 0}, {2, 0}, {5, 6}, {3, 1}, {1, 4}, {1, 5}, {0, 5}, {1, 0}, {5, 3}};

		B_947_移除最多的同行或同列石头 acion = new B_947_移除最多的同行或同列石头();
		int res = acion.removeStones(stones);
		System.out.println("res = " + res);
	}

	/**
	 * 看了提醒：并查集
	 * 真是图论月呢。
	 * --
	 * 1.将同行或者同列进行 union
	 * 2.最终判断有几个跟节点
	 * --
	 * 感觉题意有点模糊，画个图出来以后就比较清晰了：
	 * 从示例上看，只要出现在 传参中任意石头 同行/同列 -> 可以移除
	 * --
	 * 改进：
	 * 1.类似最小生成树的 Prim() 算法，从任一点出发，寻找同行同列的点
	 * 不行的，这个思路还是有问题的。
	 * --
	 * 改进II:
	 * 1.任一顶点出发，寻找
	 *
	 * @param stones
	 * @return
	 */
	public int removeStones_fail(int[][] stones) {
		//访问过的顶点集合
		Set<int[]> visitedVertexSet = new HashSet<>();
		int len = stones.length;
		int count = 0;
		for (int i = 0; i < len; i++) {
			//行号
			int ri = stones[i][0];
			//列号
			int ci = stones[i][1];
			visitedVertexSet.add(stones[i]);
			for (int j = i + 1; j < stones.length; j++) {
				//从后面去找同行同列的
				if ((ri == stones[j][0] || ci == stones[j][1]) && !visitedVertexSet.contains(stones[j])) {
					visitedVertexSet.add(stones[j]);
					count++;
				}
			}
		}

		return count;
	}

	/**
	 * 改进I：
	 * 1.从任一顶点出发，寻找同行/同列的顶点，进行 union ；
	 * 2.统计 union 中根节点的个数
	 *
	 * @param stones
	 * @return
	 */
	public int removeStones(int[][] stones) {
		int len = stones.length;
		InnerUnionFind unionFind = new InnerUnionFind(len);
		for (int i = 0; i < len; i++) {
			//行号
			int ri = stones[i][0];
			//列号
			int ci = stones[i][1];
			for (int j = i + 1; j < len; j++) {
				//从后面去找同行同列的
				if ((ri == stones[j][0] || ci == stones[j][1]) &&
						!unionFind.isSame(i, j)) {
					unionFind.union(i, j);
				}
			}
		}
		return len - unionFind.rootSet.size();
	}

	/**
	 * 内部并查集
	 * 自从遇上了图论月，每天都是一个并查集轮子
	 */
	class InnerUnionFind {
		/**
		 * 指向的都是索引
		 */
		int[] parents;
		int[] rank;
		Set<Integer> rootSet = new HashSet<>();

		public InnerUnionFind(int capacity) {
			this.parents = new int[capacity];
			this.rank = new int[capacity];
			for (int i = 0; i < capacity; i++) {
				this.parents[i] = i;
				this.rank[i] = 1;
				rootSet.add(i);
			}
		}

		/**
		 * 找到 parents 索引的根节点
		 *
		 * @param index
		 * @return
		 */
		public int find(int index) {
			if (index != parents[index]) {
				parents[index] = find(parents[index]);
			}
			return parents[index];
		}


		/**
		 * 判断根节点指向的索引是否相同
		 *
		 * @param index1
		 * @param index2
		 * @return
		 */
		public boolean isSame(int index1, int index2) {
			return find(index1) == find(index2);
		}

		public void union(int index1, int index2) {
			int p1 = find(index1);
			int p2 = find(index2);
			if (p1 == p2) {
				return;
			}
			if (rank[p1] == rank[p2]) {
				parents[p1] = p2;
				rootSet.remove(p1);
				rank[p1]++;
			} else if (rank[p1] < rank[p2]) {
				parents[p1] = p2;
				rootSet.remove(p1);
			} else {
				parents[p2] = p1;
				rootSet.remove(p2);
			}
		}
	}

}
